#include <bits/stdc++.h>
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
bool s_gnd ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
    x = 0 ;rg int f(0) ; rg char c(gc()) ;
    while(!isdigit(c)) f |= (c=='-'),c = gc() ;
    while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
    x = (f?-x:x) ;
    read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
    if(x < 0) pc('-'),x = -x ;
    do stk[++tp] = x%10,x /= 10 ; while(x) ;
    while(tp) pc(stk[tp--]^48) ; //space ;
    print(p...) ;
}
bool S_GND ;
const int N = 1e6+5 ;
int n ;
int dep[N],ans[N],f[N] ;
int ll[N],rr[N],fa[N],sta[N] ;
int ls[N],rs[N],ff[N],stt[N] ;
vector<int>pos ;
void g(int x)
{
    int l = ls[x],r = rs[x],p = fa[x] ;
    if(!sta[x])
        fa[r] = p,ls[p] = r,sta[r] = 0,sta[x] = sta[p],sta[p] = 1,fa[x] = fa[p],fa[p] = x,rs[x] = p ;
    else 
        fa[l] = p,rs[p] = l,sta[l] = 1,sta[x] = sta[p],sta[p] = 0,fa[x] = fa[p],fa[p] = x,ls[x] = p ;
}
void Dfs(int x)
{
    ans[x] += dep[x] ; if(!x) return ;
    dep[ls[x]] = dep[x]+1,Dfs(ls[x]) ;
    dep[rs[x]] = dep[x]+1,Dfs(rs[x]) ;
}
void Solve(int x)
{
    int p ;
    FOR(i,1,n,1) ls[i] = ll[i],rs[i] = rr[i],fa[i] = ff[i],sta[i] = stt[i] ;
    while(fa[x])
    {
        if(!fa[fa[x]]) g(x) ;
        else if(fa[fa[x]] && sta[x] == sta[fa[x]]) g(fa[x]),g(x) ;
        else g(x),g(x) ;
    }
    dep[x] = 0,Dfs(x) ; //FOR(i,1,n,1) print(dep[i]) ; enter ;
}
void Get(int x)
{
    if(!x) return ; pos.pb(x),Get(ll[x]) ;
}
void Solve2()
{
    Get(1) ;
    FOR(i,2,n,1)
    {
        if(i&1) f[i] = f[i-1]+2 ;
        else f[i] = f[i-1]+1 ;
    }
    int c1,c2,las = f[n] ;
    if(n&1) c1 = n/2-2,c2 = n/2 ;
    else c1 = n/2-1,c2 = n/2-2 ;
    for(auto id:pos)
        ans[id] = las,las = las+c1,swap(c1,c2) ;
    FOR(i,1,n,1) print(ans[i]),enter ;
}
signed main()
{
//cerr<<(double)(&s_gnd-&S_GND)/1024.0/1024.0 ;
	freopen("dream.in","r",stdin) ;
	freopen("dream.out","w",stdout) ;
    read(n) ; int kd = 1 ;
    FOR(i,1,n,1)
    {
        read(ll[i],rr[i]),kd &= rr[i]==0 ;
        if(ll[i]) ff[ll[i]] = i ;
        if(rr[i]) ff[rr[i]] = i,stt[rr[i]] = 1 ;
    }   
    if(n <= 2000) 
    {
        FOR(i,1,n,1) Solve(i) ; FOR(i,1,n,1) print(ans[i]),enter ;
    }
    else Solve2() ;
    return 0 ;
}